package nio;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// E find( x )   --> Return item that matches x
// E findMin( )  --> Return smallest item
// E findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order

/**
 * Implements an unbalanced binary search tree. Note that all "matching" is
 * based on the compareTo method.
 * 
 * @author Mark Allen Weiss
 */
public class BinarySearchTree<E extends Comparable<E>> {
	/**
	 * Construct the tree.
	 */
	public BinarySearchTree() {
		root = null;
	}

	/**
	 * Insert into the tree; duplicates are ignored.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void insert(final E x) {
		root = insert(x, root);
	}

	/**
	 * Remove from the tree. Nothing is done if x is not found.
	 * 
	 * @param x
	 *            the item to remove.
	 */
	public void remove(final E x) {
		root = remove(x, root);
	}

	/**
	 * Find the smallest item in the tree.
	 * 
	 * @return smallest item or null if empty.
	 */
	public E findMin() {
		return elementAt(findMin(root));
	}

	/**
	 * Find the largest item in the tree.
	 * 
	 * @return the largest item of null if empty.
	 */
	public E findMax() {
		return elementAt(findMax(root));
	}

	/**
	 * Find an item in the tree.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item or null if not found.
	 */
	public E find(final E x) {
		return elementAt(find(x, root));
	}

	/**
	 * Make the tree logically empty.
	 */
	public void makeEmpty() {
		root = null;
	}

	/**
	 * Test if the tree is logically empty.
	 * 
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * Print the tree contents in sorted order.
	 */
	public void printTree() {
		if (isEmpty()) {
			System.out.println("Empty tree");
		} else {
			printTree(root);
		}
	}

	/**
	 * Internal method to get element field.
	 * 
	 * @param t
	 *            the node.
	 * @return the element field or null if t is null.
	 */
	private E elementAt(final BinaryNode<E> t) {
		return t == null ? null : t.element;
	}

	/**
	 * Internal method to insert into a subtree.
	 * 
	 * @param x
	 *            the item to insert.
	 * @param t
	 *            the node that roots the tree.
	 * @return the new root.
	 */
	private BinaryNode<E> insert(final E x, final BinaryNode<E> in) {
		BinaryNode<E> t = in;

		/* 1 */if (t == null) {
			/* 2 */t = new BinaryNode<E>(x, null, null);
		} else if (x.compareTo(t.element) < 0) {
			/* 4 */t.left = insert(x, t.left);
		} else if (x.compareTo(t.element) > 0) {
			/* 6 */t.right = insert(x, t.right);
		} else {
			/* 8 */// Duplicate; do nothing
		}
		/* 9 */return t;
	}

	/**
	 * Internal method to remove from a subtree.
	 * 
	 * @param x
	 *            the item to remove.
	 * @param t
	 *            the node that roots the tree.
	 * @return the new root.
	 */
	private BinaryNode<E> remove(final E x, final BinaryNode<E> in) {
		BinaryNode<E> t = in;

		if (t == null) {
			return t; // Item not found; do nothing
		}
		if (x.compareTo(t.element) < 0) {
			t.left = remove(x, t.left);
		} else if (x.compareTo(t.element) > 0) {
			t.right = remove(x, t.right);
		} else if (t.left != null && t.right != null) // Two children
		{
			BinaryNode<E> min = findMin(t.right);
			min.right = remove(min.element, t.right);
			min.left = t.left;
			t = min;
		} else {
			t = (t.left != null) ? t.left : t.right;
		}
		return t;
	}

	/**
	 * Internal method to find the smallest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the smallest item.
	 */
	private BinaryNode<E> findMin(final BinaryNode<E> t) {
		if (t == null) {
			return null;
		} else if (t.left == null) {
			return t;
		}
		return findMin(t.left);
	}

	/**
	 * Internal method to find the largest item in a subtree.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the largest item.
	 */
	private BinaryNode<E> findMax(final BinaryNode<E> in) {
		BinaryNode<E> t = in;
		if (t != null) {
			while (t.right != null) {
				t = t.right;
			}
		}

		return t;
	}

	/**
	 * Internal method to find an item in a subtree.
	 * 
	 * @param x
	 *            is item to search for.
	 * @param t
	 *            the node that roots the tree.
	 * @return node containing the matched item.
	 */
	private BinaryNode<E> find(final E x, final BinaryNode<E> t) {
		if (t == null) {
			return null;
		}
		if (x.compareTo(t.element) < 0) {
			return find(x, t.left);
		} else if (x.compareTo(t.element) > 0) {
			return find(x, t.right);
		} else {
			return t; // Match
		}
	}

	/**
	 * Internal method to print a subtree in sorted order.
	 * 
	 * @param t
	 *            the node that roots the tree.
	 */
	private void printTree(final BinaryNode<E> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}

	/** The tree root. */
	private BinaryNode<E> root;

	// Test program
	public static void main(final String[] args) {
		BinarySearchTree<Integer> t = new BinarySearchTree<Integer>();
		final int NUMS = 40;
		final int GAP = 7;

		StringBuilder strB = new StringBuilder("insert: ");
		for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
			t.insert(new Integer(i));
			strB.append(i);
			strB.append(" ");
		}
		System.out.println(strB.toString());

		System.out.println("before removing: ");
		t.printTree();
		for (int i = 1; i < NUMS; i += 2) {
			t.remove(new Integer(i));
			// System.out.println("after removing: " + i);
			// t.printTree();
		}
		System.out.println("after removing all: ");
		t.printTree();

		// if ( NUMS < 40 ) {
		// t.printTree();
		// }

		if ((t.findMin()).intValue() != 2
				|| (t.findMax()).intValue() != NUMS - 2) {
			System.out.println("FindMin or FindMax error!");
		}

		for (int i = 2; i < NUMS; i += 2) {
			if ((t.find(new Integer(i))).intValue() != i) {
				System.out.println("Find error1!");
			}
		}

		for (int i = 1; i < NUMS; i += 2) {
			if (t.find(new Integer(i)) != null) {
				System.out.println("Find error2!");
			}
		}
	}
}
